#include <bits/stdc++.h>
using namespace std;

/*
2537. 统计好子数组的数目
已解答
中等
相关标签
相关企业
提示
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。

一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。

子数组 是原数组中一段连续 非空 的元素序列。

 

示例 1：

输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。
示例 2：

输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：总共有 4 个不同的好子数组：
- [3,1,4,3,2,2] 有 2 对。
- [3,1,4,3,2,2,4] 有 3 对。
- [1,4,3,2,2,4] 有 2 对。
- [4,3,2,2,4] 有 2 对。
 

提示：

1 <= nums.length <= 105
1 <= nums[i], k <= 109
*/

// 法一
class Solution {
	public:
	using ll = long long;
	long long countGood(vector<int>& nums, int k) {
		unordered_map<int, int> count;  // 记录窗口内各元素的出现次数
		ll ans = 0;
		ll total_pairs = 0;     // 当前窗口的总对数
		int left = 0;   // 滑动窗口左指针

		for (int right = 0; right < nums.size(); ++right) {
			int num = nums[right];
			// 当前元素之前出现的次数 就是 新增的对数
			total_pairs += count[num];
			count[num]++;   // 更新当前元素的频次
			// 总对数>=k 收缩左窗口
			while (total_pairs >= k) {
				int left_num = nums[left];
				int left_cnt = count[left_num];
				// 左元素移出之后 对数减少(left_cnt - 1)
				total_pairs -= (left_cnt - 1);
				count[left_num]--;
				left++;
			}
			// 均满足条件
			ans += left;
		}
		return ans;
	}
};

// 法二
class Solution {
	public:
	long long countGood(vector<int>& a, int k) {
		// 哈希表记录窗口内各元素的出现次数，键为元素值，值为出现次数
		unordered_map<int, int> lst;
		int n = a.size();
		lst.reserve(n * 2); // 预分配空间避免扩容影响性能
		long long ans = 0;  // 存储最终结果
		
		// 滑动窗口：i为右指针，j为左指针
		for (int j = 0, i = 0; i < n; ++i) {
			// 将a[i]纳入窗口：新增的对数等于该元素之前的出现次数
			// 例如，若a[i]之前出现2次，则新增2对，故k需减2（原k是剩余需要满足的对数）
			k -= lst[a[i]]++; // 先取当前计数再自增
			
			// 当窗口内对数 >=k 时（即k<=0），收缩左指针j
			while (k <= 0) {
				// 移出a[j]前，其出现次数减1，减少的对数为减后的值
				// 例如，若a[j]原出现3次，移出后剩2次，减少2对，故k加2
				k += --lst[a[j]];
				++j; // 左指针右移
			}
			
			// 此时，所有左端点[0, j-1]与当前右端点i形成的子数组均满足条件
			// 例如j=3时，说明有3个左端点（0,1,2）满足条件
			ans += j;
		}
		return ans;
	}
};